☆ Comptage de chaînes : preuve de la propriété - Vers le supérieur

Propriété Nombre de chaînes de longueur  $k$ qui relient le sommet  $i$ au sommet $j$

Soit  $n$ et  $k$ deux entiers naturels non nuls, et  $A$ la matrice d’adjacence d’un graphe  $G$ d’ordre  $n$ dont les sommets sont numérotés de  $1$ à $n$ , puis rangés dans l’ordre croissant de leurs numéros.
𝑀 est une matrice carrée de taille $n\times n$ .

Le coefficient de la  $i$ -ème ligne et de la  $j$ -ème colonne de la matrice  $A^k$ donne le nombre de chaînes (ou de chemins) de longueur  $k$ reliant le sommet  $i$ au sommet $j$ .

On appellera $a_{ij}^{(k)}$  le coefficient de la  $i^{ieme}$ ligne et de la  $j^{ieme}$ colonne de la matrice  $A^k$ (attention, dans l’écriture $a_{ij}^{(k)}$ , $(k)$  n’est pas un exposant mais indique qu’on parle de la matrice $A^k$ ).

Posons  $P(k)$ la propriété : « Pour tout entier $i$ ,  $1\le i\le n$ et tout entier $j$ , $1\le j\le n$ , le coefficient  $a_{ij}^{(k)}$ de la  $i$ -ème ligne et de la $j$ -ème colonne de la matrice  $A^k$ donne le nombre de chaînes (ou de chemins) de longueur  $k$ reliant le sommet  $i$ au sommet  $j$ . »

Démonstration

On va démontrer par récurrence que  $P(k)$ est vraie pour tout  $k\in {\mathbb{N}}^{\ast }$ .

Initialisation 
$P(1)$ est vraie car  $A^1=A$ et c’est la définition de la matrice d’adjacence.

Hérédité
Soit  $k\in {\mathbb{N}}^{\ast }$ tel que  $P(k)$ est vraie, a-t-on aussi $P(k+1)$ est vraie ?
Soit  $i_0$ et  $j_0$ deux entiers compris entre  $1$ et $n$ .
On veut compter le nombre de chaînes de longueur $k+1$   reliant le sommet numéroté  $i_0$ au sommet numéroté $j_0$ .
Une telle chaîne est composée de $k$ arêtes reliant le sommet numéroté  $i_0$ à un autre sommet numéroté  $p$ (avec $1\le p\le n$ ) et d’une dernière arête reliant le sommet numéroté $p$ au sommet numéroté $j_0$ .
Or, d’après l’hypothèse de récurrence, le nombre de chaînes de longueur $k$ reliant le sommet numéroté  $i_0$ au sommet numéroté  $p$ est égal à  $a_{i_{0}p}^{(k)}$ .
De plus, le nombre de chaînes de longueur  $1$ reliant le sommet numéroté  $p$ au sommet numéroté  $j_0$ est égal à $a_{p{j}_0}=a_{p{j}_0}^{(1)}$  par définition de la matrice d’adjacence.
Pour dénombrer ces chaînes, on doit donc sommer les termes  $a_{i_{o}p}^{(k)}\times a_{p{j}_0}$ pour  $p$ allant de  $1$ à $n$ .
D’après la définition du produit de matrices,  ${\displaystyle \sum _{p=1}^n{a}_{i_{o}p}^{(k)}\times a_{p{j}_0}=a_{i_0{j}_0}^{(k+1)}}$ .
On a donc prouvé que, si $P(k)$  est vraie, alors $P(k+1)$  est vraie. La propriété est héréditaire.

Conclusion
Cette propriété est initialisée au rang 1 et héréditaire à partir de ce rang, elle est donc vraie pour tout $k\in {\mathbb{N}}^{\ast }$ .